skip to main content
10.1145/62212.62213acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free Access

Completeness theorems for non-cryptographic fault-tolerant distributed computation

Published:01 January 1988Publication History

ABSTRACT

Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that:

  • If no faults occur, no set of size t < n/2 of players gets any additional information (other than the function value),

  • Even if Byzantine faults are allowed, no set of size t < n/3 can either disrupt the computation or get additional information.

Furthermore, the above bounds on t are tight!

References

  1. BL.M. Ben-Or and N. Linial, Collective coin flipping, FOCS86.Google ScholarGoogle Scholar
  2. CCD.D. Chaum, C. Crepeau and I. Damgard, Multiparty unconditionally secure protocols, These proceedings. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. DH.W. Diffie and M. E. Helman, New directions in cryptography, iEEE Trt~ns. Inform. Theory, VoI.IT-22,pp.644-654, 1976.Google ScholarGoogle Scholar
  4. DS.D. Dolev and R. St. rong, Polynomial algorithms for multiple processor agreement. STOC82. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. FM.P. Fcldlllan and S. Micali, Opt. inlal algoritllrns for Byzantine agreement, These proceediligs.Google ScholarGoogle Scholar
  6. GMW1.O. Goldriech, S. Micali and A. Wigderson, Proofs that yield nothing but the validity of the assertion, and a methodology of cryptographic protocol design, FOCS86, pp. 174-187. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. GMW2.O. Goldriech, S. Micali and A. Wigderson, How to play any mental game, STOC87, pp. 218-229. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. GMR.S. Goldwasser, S. Micali and C. Rackoff, The knowledge complexity of interactive proof systems, STOC85, pp. 291-304. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. PSL.M. Pease, R. Shostak and L. Lamport, Reaching agreement in the presence of faults, JACM Vol. 27, pp. 228-234, (1980). Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. PW.W. W. Peterson and E. J. Weldon, Error correcting codes, Second Ed., MiT Press, (1972).Google ScholarGoogle Scholar
  11. Sh.A. Sha!lfir, How to share tt secret, CACM, 22, pp. 612-613, (1979). Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Y1.A. C. Yao, How to generate and exchange secrets~ STOC86.Google ScholarGoogle Scholar
  13. Y2.A. (2. Yao, On the succession problem for Byzantine Generals, manuscript, (1983).Google ScholarGoogle Scholar

Index Terms

  1. Completeness theorems for non-cryptographic fault-tolerant distributed computation

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing
          January 1988
          553 pages
          ISBN:0897912640
          DOI:10.1145/62212

          Copyright © 1988 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 1 January 1988

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • Article

          Acceptance Rates

          STOC '88 Paper Acceptance Rate53of192submissions,28%Overall Acceptance Rate1,469of4,586submissions,32%

          Upcoming Conference

          STOC '24
          56th Annual ACM Symposium on Theory of Computing (STOC 2024)
          June 24 - 28, 2024
          Vancouver , BC , Canada

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader